An autonomous vehicle is a vehicle that is capable of sensing its environment and navigating without human input. In particular, an autonomous vehicle can observe its surrounding environment using a variety of sensors and can attempt to comprehend the environment by performing various processing techniques on data collected by the sensors. Given knowledge of an environment proximate to the autonomous vehicle, the autonomous vehicle can identify an appropriate motion plan through such environment. One or more of such autonomous vehicles can be used to provide a vehicle-based service in which an autonomous vehicle(s) can autonomously navigate through an environment between a starting location and an ending location of the provided service.